package __二叉树

/*
*
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历，
postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

中序+后续遍历, 重构二叉树

示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]
*/
var (
	hash map[int]int //全局hashmap
)

func buildTree(inorder []int, postorder []int) *TreeNode {

	hash = make(map[int]int) //初始化map

	for i, v := range inorder { // 保存中序序列的数值对应位置
		hash[v] = i
	}

	// 以左闭右闭的原则进行切分  inorder:中序数组  postorder:后序数组 len(postorder)-1:根节点在后续数组的下标 0:本轮中序数组起始 len(inorder)-1:本轮中序数组结束位置
	root := rebuild(inorder, postorder, len(postorder)-1, 0, len(inorder)-1)

	return root
}

// rootIdx表示根节点在后序数组中的索引，l, r 表示在中序数组中的前后切分点
func rebuild(inorder []int, postorder []int, rootIdx int, l, r int) *TreeNode {
	if l > r { // 说明没有元素，返回空树
		return nil
	}
	if l == r { // 只剩唯一一个元素，直接返回
		return &TreeNode{Val: inorder[l]}
	}

	rootV := postorder[rootIdx]   // 根据后序数组找到根节点的值
	rootIn := hash[rootV]         // 找到根节点在对应的中序数组中的位置
	root := &TreeNode{Val: rootV} // 构造根节点

	// 重建左节点和右节点
	root.Left = rebuild(inorder, postorder, rootIdx-(r-rootIn)-1, l, rootIn-1)
	root.Right = rebuild(inorder, postorder, rootIdx-1, rootIn+1, r)
	return root
}
